
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> s;
        sort(nums.begin(),nums.end());
        for(int i=nums.size()-1;i>=2; )
        {
            if(nums[i]<0) break;//小优化
            int t=-nums[i];
            int l=0;
            int r=i-1;
            while(l<r)
            {
                if(nums[l]+nums[r]>t)
                {
                    r--;
                    while(nums[r]==nums[r+1]&&r>l) r--;
                }
                else if(nums[l]+nums[r]<t)
                {
                    l++;
                    while(nums[l]==nums[l-1]&&l<r) l++;
                }
                else{
                    vector<int> s1{nums[l],nums[r],nums[i]};
                    s.push_back(s1);
                    l++;
                    while(nums[l]==nums[l-1]&&l<r) l++;
                    r--;
                    while(nums[r]==nums[r+1]&&r>l) r--;
                }
            }
            i--;
            while(nums[i+1]==nums[i]&&i>=1) i--;
        }
        return s;
    }
};